{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Search Insert Position"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: searchInsert"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #搜索插入位置"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。</p>\n",
    "\n",
    "<p>请必须使用时间复杂度为 <code>O(log n)</code> 的算法。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [1,3,5,6], target = 5\n",
    "<strong>输出:</strong> 2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [1,3,5,6], target = 2\n",
    "<strong>输出:</strong> 1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [1,3,5,6], target = 7\n",
    "<strong>输出:</strong> 4\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>-10<sup>4</sup> &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>nums</code> 为&nbsp;<strong>无重复元素&nbsp;</strong>的&nbsp;<strong>升序&nbsp;</strong>排列数组</li>\n",
    "\t<li><code>-10<sup>4</sup> &lt;= target &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [search-insert-position](https://leetcode.cn/problems/search-insert-position/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [search-insert-position](https://leetcode.cn/problems/search-insert-position/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,5,6]\\n5', '[1,3,5,6]\\n2', '[1,3,5,6]\\n7']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: list[int], target: int) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if nums[-1] < target:\n",
    "                return len(nums)\n",
    "            if nums[0] > target:\n",
    "                return 0\n",
    "            if nums[i] == target:\n",
    "                return i\n",
    "            elif nums[i]<target and nums[i+1]>target:\n",
    "                return i+1\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    nums = [1,3,5,6]\n",
    "    target = 7\n",
    "    solution = Solution()\n",
    "    resualt = solution.searchInsert(nums, target)\n",
    "    print(resualt)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        i=0\n",
    "        if len(nums)>=2:\n",
    "            while len(nums)>=2:\n",
    "                half=int(len(nums)/2)#奇数是中间，偶数找前面\n",
    "                if target>nums[half]:\n",
    "                    del nums[:half]\n",
    "                    i+=half\n",
    "                elif target<nums[half]:\n",
    "                    del nums[half:]\n",
    "                else:\n",
    "                    return i+half\n",
    "            if target>nums[0]:\n",
    "                return i+1\n",
    "            else:\n",
    "                return i\n",
    "        else:\n",
    "            if target>nums[0]:\n",
    "                return i+1\n",
    "            else:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        imin, imax = 0, n-1 # n是末尾长度, -1了之后\n",
    "        while imin <= imax:\n",
    "            i = int((imin+imax)/2)\n",
    "            print('i:', i, 'max:', imax, 'min',imin)\n",
    "            if nums[i] < target:\n",
    "                imin = i+1\n",
    "            elif nums[i] > target:\n",
    "                imax = i-1\n",
    "            else:\n",
    "                return i\n",
    "        return imin\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # if nums[0]>=target:\n",
    "        #     return 0\n",
    "        # for i in range(len(nums)-1):\n",
    "        #     if nums[i]<target and nums[i+1]>=target:\n",
    "        #         return i+1\n",
    "        # return len(nums)\n",
    "     \n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]>=target:\n",
    "                return i\n",
    "        return len(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        p = 0\n",
    "        try:\n",
    "            while(nums[p] < target):\n",
    "                p += 1\n",
    "            return p\n",
    "        except:\n",
    "            return p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        length = len(nums)\n",
    "        point = length-1\n",
    "        while nums[point] > target and point >= 0:\n",
    "            point -= 1\n",
    "        if nums[point] == target:\n",
    "            return point\n",
    "        else:\n",
    "            return point+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        if len(nums) == 0 or target <= nums[0]:\n",
    "            return 0\n",
    "        for i in range(0, len(nums)):\n",
    "            if i == len(nums)-1:\n",
    "                return i + 1\n",
    "            if target > nums[i] and target <= nums[i+1]:\n",
    "                return i+1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if nums[0] >= target:\n",
    "            return 0\n",
    "        elif nums[-1] < target:\n",
    "            return len(nums)\n",
    "        \n",
    "        left = 0\n",
    "        right = len(nums)\n",
    "        \n",
    "        temp = 0\n",
    "        while(left < right):\n",
    "            mid = left + (right - left)//2\n",
    "            print(left, mid, right)\n",
    "            if nums[mid] == target:\n",
    "                return mid\n",
    "            elif nums[mid] > target:\n",
    "                right -= 1\n",
    "            else:\n",
    "                left += 1\n",
    "\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums, target):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type target: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        dic = dict(zip(nums,range(len(nums))))\n",
    "        if target in nums:\n",
    "            return dic[target]\n",
    "        else:\n",
    "            if target < nums[0]:\n",
    "                return 0\n",
    "            elif target > nums[-1]:\n",
    "                return len(nums)\n",
    "            else:\n",
    "                for i in range(len(nums)):\n",
    "                    if nums[i] < target < nums[i+1]:\n",
    "                        return i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: 'List[int]', target: 'int') -> 'int':\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] >= target:\n",
    "                return i\n",
    "        return len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: 'List[int]', target: 'int') -> 'int':\n",
    "        # return bisect.bisect_left(nums, target)\n",
    "        lo = 0\n",
    "        hi = len(nums)\n",
    "        while lo < hi:\n",
    "            mid = (lo+hi) // 2\n",
    "            if nums[mid] < target:\n",
    "                lo = mid + 1\n",
    "            else:\n",
    "                hi = mid\n",
    "        return lo\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        if target not in nums:\n",
    "            nums.append(target)\n",
    "            nums.sort()\n",
    "        return nums.index(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        left, right = 0, len(nums)\n",
    "        while left < right:\n",
    "            mid = left + (right - left)//2\n",
    "            num = nums[mid]\n",
    "            if target > num:\n",
    "                left = mid + 1\n",
    "            elif target < num:\n",
    "                right = mid\n",
    "            else:   \n",
    "                return mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        \n",
    "        if not nums: return 0\n",
    "        length = len(nums)-1\n",
    "        left, right = 0, length\n",
    "        \n",
    "        while True:\n",
    "            \n",
    "            mid = left + (right-left)//2\n",
    "            \n",
    "            if nums[mid]==target:\n",
    "                return mid\n",
    "            elif nums[mid]>target:\n",
    "                if mid==0 or nums[mid-1]<target:\n",
    "                    return mid\n",
    "                right = mid-1\n",
    "            else:\n",
    "                if mid==length or nums[mid+1]>target:\n",
    "                    return mid+1\n",
    "                \n",
    "                left = mid+1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        if target in nums:\n",
    "            return nums.index(target)\n",
    "        nums.sort()\n",
    "        if target <= nums[0]:\n",
    "            return 0\n",
    "        if target >= nums[-1]:\n",
    "            return len(nums)\n",
    "        for index,num in enumerate(nums):\n",
    "            if target>= num and target<= nums[index+1]:\n",
    "                return index + 1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        if nums[-1] < target:\n",
    "            return len(nums)\n",
    "        for i, v in enumerate(nums):\n",
    "\n",
    "            if v >= target:\n",
    "                return i\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] == target or nums[i] > target:\n",
    "                return i\n",
    "        if nums[-1] < target:\n",
    "            return len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        i = 0\n",
    "        while i < len(nums):\n",
    "            if nums[i] == target or nums[i] > target:\n",
    "                return i\n",
    "            i += 1\n",
    "        if nums[-1] < target:\n",
    "            return len(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        def find(b,e):\n",
    "            if b == e:\n",
    "                return b\n",
    "            mid = (b+e) // 2\n",
    "            if nums[mid] == target:\n",
    "                return mid\n",
    "            elif nums[mid] > target:\n",
    "                return find(b,mid)\n",
    "            else:\n",
    "                return find(mid+1,e)\n",
    "        return find(0,len(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        val=set(nums)\n",
    "        if target in val:\n",
    "            return nums.index(target)\n",
    "        else:\n",
    "            for i in nums:\n",
    "                if i>target:\n",
    "                    return nums.index(i)\n",
    "            return len(nums)\n",
    "'''\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        # 不管这个数在不在里面，直接append\n",
    "        nums.append(target)\n",
    "        # 然后再排序\n",
    "        nums.sort()\n",
    "        # 最后返回查找的index\n",
    "        return nums.index(target)\n",
    "'''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        return bisect_left(nums, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        if nums:\n",
    "            for i in range(len(nums)):\n",
    "                if nums[i] >= target:\n",
    "                    return i\n",
    "            return len(nums)\n",
    "        else:\n",
    "            return 0\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        left,right=0,len(nums)-1\n",
    "\n",
    "        while(left<=right):\n",
    "            mid=(left+right)//2\n",
    "            if nums[mid]<target:\n",
    "                left=mid+1\n",
    "            elif nums[mid]>target:\n",
    "                right=mid-1\n",
    "            else:\n",
    "                return mid  \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        left = 0 \n",
    "        right = len(nums)\n",
    "        while left<right:\n",
    "            mid = left + (right - left)//2\n",
    "            if nums[mid]>=target:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        l = 0\n",
    "        r = len(nums) - 1\n",
    "        while l <= r:\n",
    "            mid = (r - l) // 2 + l\n",
    "            if nums[mid] == target:\n",
    "                return mid\n",
    "            elif nums[mid] < target:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        def two_find(begin,end,target):\n",
    "            mod=(begin+end)//2\n",
    "            if begin<end:\n",
    "                if target<nums[mod]:\n",
    "                    return two_find(begin,mod-1,target)\n",
    "                elif target>nums[mod]:\n",
    "                    return two_find(mod+1,end,target)\n",
    "                else:\n",
    "                    return mod\n",
    "            else:\n",
    "                if nums[mod]<target:\n",
    "                    mod+=1\n",
    "                return mod\n",
    "        if target<=nums[0]:\n",
    "            return 0\n",
    "        return two_find(0,len(nums)-1,target)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        dic = {}\n",
    "        if target < min(nums):\n",
    "            return 0\n",
    "        if target > max(nums):\n",
    "            return len(nums)\n",
    "        for i in range(len(nums)):\n",
    "            if i < len(nums)-1 and target > nums[i] and target < nums[i+1]:\n",
    "                return i+1\n",
    "            dic[nums[i]] = i\n",
    "        if target in dic:\n",
    "            return dic[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        l, r = 0, n - 1\n",
    "        res = n\n",
    "        while l <= r:\n",
    "            mid = l + (r - l) // 2\n",
    "            if nums[mid] >= target:\n",
    "                res = mid\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        left, right = 0, len(nums) #采用左闭右开区间[left,right)\n",
    "        while left < right: # 右开所以不能有=,区间不存在\n",
    "            mid = left + (right - left)//2 # 防止溢出, //表示整除\n",
    "            if nums[mid] < target: # 中点小于目标值,在右侧,可以得到相等位置\n",
    "                left = mid + 1 # 左闭,所以要+1\n",
    "            else:\n",
    "                right = mid # 右开,真正右端点为mid-1\n",
    "        return left # 此算法结束时保证left = right,返回谁都一样\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def searchInsert(self, nums: List[int], target: int) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            pos = 0 if target <= nums[0] else 1\n",
    "            return pos\n",
    "        left, right = n//2-1, n//2\n",
    "        n1, n2 = nums[left], nums[right]\n",
    "        if target <= n1:\n",
    "            new_nums = nums[: right]\n",
    "            return self.searchInsert(new_nums, target)\n",
    "        elif n1<= target < n2:\n",
    "            return right\n",
    "        else:\n",
    "            new_nums = nums[right: ]\n",
    "            # print(left)\n",
    "            return self.searchInsert(new_nums, target) + right"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
